// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-06 14:33
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;

public class DiameterOfBinaryTree {
    /**
     * 二叉树的直径 = 左子树最长路径 + 右子树最长路径
     * 二叉树的直径不一定经过根节点
     */
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getMaxPath(root.left) + getMaxPath(root.right), Math.max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right)));
    }

    private int getMaxPath(TreeNode root) {
        if (root == null) {
            // 每一棵树的叶子节点可以假设为null节点
            return 0;
        }
        int leftMax = 0;
        int rightMax = 0;
        if (root.left != null) {
            leftMax += getMaxPath(root.left);
        }
        if (root.right != null) {
            rightMax += getMaxPath(root.right);
        }
        return Math.max(leftMax, rightMax) + 1;
    }
}
